#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
// #define ONLINE_GUDGE
using namespace std;
const int N = 1000005, M = 4000005, MOD = 100003, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], ne[M], idx;
int dist[N];
bool st[N]; 
int ans[N];

void AddEdge(int a, int b)
{ e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

void bfs()
{
    memset(st, 0, sizeof st);

    queue<int> q;

    q.push(1);
    dist[1] = 0;
    ans[1] = 1;
    st[1] = true;

    while(q.size())
    {
        auto u = q.front();q.pop();

        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if(!st[v]){
                dist[v] = dist[u] + 1;
                ans[v] = ans[u];                
                st[v] = true;
                q.push(v);
                
            }
            else if (dist[v] == dist[u] + 1) ans[v] = (ans[u] + ans[v]) % MOD; // 其本身就是最短路径
        }
    }
}

int main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);
    memset(h, -1, sizeof h);

    cin >> n >> m;  

    while(m--){
        int a, b; cin >> a >> b;

        AddEdge(a, b); AddEdge(b, a);
    }

    bfs();
    for (int i = 1;i <= n;i++) cout << ans[i] << endl;

    return 0;
}